package cn.edu.xjtu.work.sortArrayByParityII;

/**
 * 922. 按奇偶排序数组 II
 * 
 * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
 * 
 * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
 * 
 * 你可以返回任何满足上述条件的数组作为答案。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        int[] nums = { 2, 1, 4, 3, 6, 5 };
        System.out.println(solu.sortArrayByParityII(nums));
    }

    public int[] sortArrayByParityII(int[] nums) {
        int j = 1;
        for (int i = 0; i < nums.length; i += 2) {
            if (nums[i] % 2 == 1) {
                while (j < nums.length && nums[j] % 2 == 1) {
                    j += 2;
                }
                if (j >= nums.length) {
                    break;
                }
                swap(nums, i, j);
            }
        }
        return nums;
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

}
